We investigate decoherence in the quantum kicked rotator (modelling cold atoms in a pulsed optical field) subjected to noise with power-law tail waiting-time distributions of variable exponent (Levy noise). We demonstrate the existence of a regime of nonexponential decoherence where the notion of a decoherence rate is ill-defined. In this regime, dynamical localization is never fully destroyed, indicating that the dynamics of the quantum system never reaches the classical limit. We show that this leads to quantum subdiffusion of the momentum, which should be observable in an experiment.